package com.algorithm.code.list;

import java.util.ArrayList;
import java.util.List;

/**
 * @description leetcode 第234题，回文队列
 * https://leetcode-cn.com/problems/palindrome-linked-list/solution/
 * @program: sudy
 * @description: 回文链表
 * @author:
 * @create: 2020-01-22 18:42
 **/
public class PalindromeList {



    public static void main(String[] args) {

    }

    public boolean isPalindrome(ListNode head) {

        if (head == null) {
            return false;
        }

        return methodArray(head);
    }

    /***
     * @Description: 采用数组的方式构建
     * 采用双数组指针法
     * @Param: [head]
     * @return: boolean
     * @Author: kukuxiahuni
     * @Date: 2020/1/22
     */
    private boolean methodArray(ListNode head) {

        List<Integer> arrayList = new ArrayList<>();

        ListNode p = head;
        while (p != null) {
            arrayList.add(p.val);
            p = p.next;
        }

        int begin = 0, end = arrayList.size() - 1;

        while (begin <= end) {
            if (!arrayList.get(begin).equals(arrayList.get(end))) {
                return false;
            }
            ++begin;
            --end;
        }
        return true;
    }

    /**
     * @Description: 方案二：
     * 1. 找到链表的中间节点
     * 2. 反转中间节点之后的链表
     * 3. 开始判断
     * @Param: [listNode]
     * @return: boolean
     * @Author: kukuxiahuni
     * @Date: 2020/1/22
     */
    private boolean reverseList(ListNode listNode) {

        ListNode slow = listNode.next, fast = listNode;

        //1. 先找到链表的中间节点, 主要找到的是后一个节点
        //2. 奇数个节点就是中间节点
        //3. 偶数个节点要保证前半部分比后半部分多一个节点

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //反转链表, 1其中pre位头结点
        ListNode pre = null, cur = slow;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }


        ListNode p = listNode, q = pre;

        while (q!=null){
            if (p.val != q.val) {
                return false;
            }

            p = p.next;
            q = q.next;
        }

        return true;
    }


}
